package org.example.LeetCode;


import java.util.Arrays;
import java.util.Comparator;

/**
    * 给定一个区间的集合 intervals ，其中 intervals[i] = [starti, endi] 。返回 需要移除区间的最小数量，使剩余区间互不重叠 。
     *
     * 注意 只在一点上接触的区间是 不重叠的。例如 [1, 2] 和 [2, 3] 是不重叠的。
     *
    *输入: intervals = [[1,2],[2,3],[3,4],[1,3]]
     * 输出: 1
     * 解释: 移除 [1,3] 后，剩下的区间没有重叠。
     *
     *
     输入: intervals = [ [1,2], [1,2], [1,2] ]
     输出: 2
     解释: 你需要移除两个 [1,2] 来使剩下的区间没有重叠。

     输入: intervals = [ [1,2], [2,3] ]
     输出: 0
     解释: 你不需要移除任何区间，因为它们已经是无重叠的了。

**/

public class leetCode_435 {
    public static void main(String[] args) {
        int[][] intervals = {{1, 2}, {2, 3}, {3, 4}, {1, 3}};
        int[][] intervals1 = {{1, 2}, {1, 2}, {1, 2}};
        System.out.println(eraseOverlapIntervals(intervals1));
    }
    public static int eraseOverlapIntervals(int[][] intervals) {
        /***
         需要移除区间的最小数量，使剩余区间互不重叠
         利用贪心算法 得到局部最优解
         找到最小的区间 将区间进行排序
         1、首先排除相同的区间
         2、根据区间的第二个数据进行排序
         3、举例 [1,3] [2,4]  前一个数据的尾巴需要小于第二个数据的开头
         intervals[0][1]<intervals[1][0]

        **/
        // 按照区间的第二个数进行排序
        Arrays.sort(intervals, Comparator.comparingInt(item -> item[1]));

        int count = 0;
        int min = intervals[0][1];
        for (int i = 1; i < intervals.length; i++) {
            if (intervals[i][0]<min){
                count++;
            }else {
                min = intervals[i][1];
            }
        }
        return count;
    }
}
